/*    Copyright 2010 Tobias Marschall
 *
 *    This file is part of MoSDi.
 *
 *    MoSDi is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    MoSDi is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoSDi.  If not, see <http://www.gnu.org/licenses/>.
 */

package mosdi.util;

import java.math.BigInteger;
import java.util.ArrayList;

public class Combinatorics {

	private ArrayList<Double> logFactorials;
	private ArrayList<BigInteger> bigIntFactorials;
	private final static BigInteger maxLong = BigInteger.valueOf(Long.MAX_VALUE); 
	private static Combinatorics instance = null;
	
	private Combinatorics() {
		logFactorials = new ArrayList<Double>(1000);
		logFactorials.add(0.0);
		logFactorials.add(0.0);
		bigIntFactorials = new ArrayList<BigInteger>(1000);
		bigIntFactorials.add(BigInteger.ONE);
		bigIntFactorials.add(BigInteger.ONE);
	}
	
	private static Combinatorics getInstance() {
		if (instance==null) {
			instance = new Combinatorics();
		}
		return instance;
	}
	
	private double computeLogFactorial(int n) {
		for (int x=logFactorials.size(); x<=n; ++x) {
			logFactorials.add(logFactorials.get(x-1)+Math.log(x));
		}
		return logFactorials.get(n);
	}

	private BigInteger computeBigIntFactorial(int n) {
		for (int x=bigIntFactorials.size(); x<=n; ++x) {
			bigIntFactorials.add(bigIntFactorials.get(x-1).multiply(BigInteger.valueOf(x)));
		}
		return bigIntFactorials.get(n);
	}

	public static double logFactorial(int x) {
		return getInstance().computeLogFactorial(x);
	}

	public static BigInteger bigIntFactorial(int x) {
		return getInstance().computeBigIntFactorial(x);
	}

	public static long factorial(int x) {
		switch (x){
		case 0: return 1L;
		case 1: return 1L;
		case 2: return 2L;
		case 3: return 6L;
		case 4: return 24L;
		case 5: return 120L;
		case 6: return 720L;
		case 7: return 5040L;
		case 8: return 40320L;
		case 9: return 362880L;
		case 10: return 3628800L;
		case 11: return 39916800L;
		case 12: return 479001600L;
		case 13: return 6227020800L;
		case 14: return 87178291200L;
		case 15: return 1307674368000L;
		case 16: return 20922789888000L;
		case 17: return 355687428096000L;
		case 18: return 6402373705728000L;
		case 19: return 121645100408832000L;
		case 20: return 2432902008176640000L;
		default: throw new IllegalArgumentException("Number too large");
		}
	}
	
	/** Computes the logarithm of "n choose k". */
	public static double logBinomial(int n, int k) {
		if (n<k) throw new IllegalArgumentException("It must be n>=k.");
		Combinatorics in = getInstance(); 
		return in.computeLogFactorial(n)-(in.computeLogFactorial(k)+in.computeLogFactorial(n-k));
	}

	/** Computes "n choose k". */
	public static BigInteger bigIntBinomial(int n, int k) {
		if (n<k) throw new IllegalArgumentException("It must be n>=k.");
		Combinatorics in = getInstance(); 
		return in.computeBigIntFactorial(n).divide(in.computeBigIntFactorial(k)).divide(in.computeBigIntFactorial(n-k));
	}

	/** Computes "n choose k". */
	public static long binomial(int n, int k) {
		BigInteger result = bigIntBinomial(n,k);
		if (result.compareTo(maxLong)>=0) throw new IllegalArgumentException("Number too large");
		return result.longValue();
	}

	/** Computes "n choose k_1,...,k_i". */
	public static double logMultinomial(int n, int[] k) {
		Combinatorics in = getInstance();
		int sum = 0;
		double x = in.computeLogFactorial(n);
		for (int i : k) {
			x -= in.computeLogFactorial(i);
			sum+=i;
		}
		if (sum!=n) throw new IllegalArgumentException();
		return x;
	}

	/** Computes "n choose k_1,...,k_i". */
	public static BigInteger bigIntMultinomial(int n, int[] k) {
		Combinatorics in = getInstance();
		int sum = 0;
		BigInteger x = in.computeBigIntFactorial(n);
		for (int i : k) {
			x = x.divide(in.computeBigIntFactorial(i));
			sum+=i;
		}
		if (sum!=n) throw new IllegalArgumentException();
		return x;
	}
	
	/** Computes "n choose k_1,...,k_i". */
	public static long multinomial(int n, int[] k) {
		BigInteger result = bigIntMultinomial(n,k);
		if (result.compareTo(maxLong)>=0) throw new IllegalArgumentException("Number too large");
		return result.longValue();
	}

}
